GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Algorithmus von Cohen-Sutherland</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Algorithmus von Cohen-Sutherland</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Algorithmus von Cohen-Sutherland ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zum Abschneiden (<a href="Clipping_(Computergrafik)" title="Clipping (Computergrafik)">Clipping</a>) von Linien an einem <a href="Rechteck" title="Rechteck">Rechteck</a>. Er ist nach seinen Erfindern <a href="Danny_Cohen_(Ingenieur)" title="Danny Cohen (Ingenieur)">Danny Cohen</a> und <a href="Ivan_Sutherland" title="Ivan Sutherland">Ivan Sutherland</a> benannt. Der Algorithmus gilt als populärster, wenn auch nicht effizientester für seine Zwecke. Er eignet sich besonders für Fälle, in denen ein hoher Anteil der zu clippenden Linien inner- oder außerhalb des Rechtecks liegt.

<div class="mw-heading mw-heading2"><h2 id="Schritte">Schritte</h2></div>

Zuerst werden jeweils für die beiden Endpunkte der zu zeichnenden Linie vier <a href="Flag_(Informatik)" title="Flag (Informatik)">Flags</a> ermittelt, die gesetzt werden, wenn sich der Endpunkt links des Rechtecks, rechts davon, darunter oder darüber befindet. Ist keines der Flags gesetzt, dann liegen beide Endpunkte innerhalb des Rechtecks, es ist kein Clipping notwendig und die Linie kann einfach gezeichnet werden.

Wenn dieser triviale Fall nicht eintritt, werden im nächsten Schritt die einander entsprechenden Flags beider Endpunkte angesehen. Ist mindestens eines dieser Flags bei beiden Endpunkten gesetzt, so befindet sich die gesamte Linie außerhalb des Rechtecks und die Linie braucht nicht gezeichnet zu werden.

Wenn auch dieser einfache Fall nicht auftritt, wird der Schnittpunkt einer (beliebigen) Rechteck-Seite mit dem Liniensegment berechnet und der überlappende Teil erneut getestet (und eventuell gekürzt), bis schließlich beide Punkte innerhalb des Rechtecks liegen.

<div class="mw-heading mw-heading2"><h2 id="Implementierung">Implementierung</h2></div>

Das folgende Programm gibt ein Beispiel einer <a href="Implementierung" title="Implementierung">Implementierung</a> des Cohen-Sutherland-Algorithmus in C++, anhand dessen man die Funktionsweise gut nachvollziehen kann.

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre> /*----------------------------------------------------------------------------------------

Clipping der zwei X,Y Koordinaten einer Linie innerhalb eines zweidimensionalen

Clipping Rechtecks XMin,YMin,XMax,YMax nach Cohen Sutherland.

Nach Ablauf der Funktion sind die Koordinaten der beiden Punkte so geclippt, dass sie

innerhalb des Clipping Rechtecks liegen und der Linie entsprechen, die übrig bleibt,

wenn man die außerhalb liegenden Teile abschneidet.

Falls kein Teil der Linie das Clipping Rechteck überstreicht, liefert die Funktion den

Wert FALSE zurück.

x1,y1  : Koordinate des Anfangspunktes der Linie

x2,y2  : Koordinate des Endpunktes der Linie

return  : FALSE Linie ist komplett geclippt und braucht nicht gezeichnet zu werden.

TRUE Die Koordinaten sind geclippt und die Linie kann jetzt gezeichnet werden

------------------------------------------------------------------------------------------*/

#define CLIPLEFT 1 // Binär 0001

#define CLIPRIGHT 2 // 0010

#define CLIPLOWER 4 // 0100

#define CLIPUPPER 8 // 1000

bool clipline(int &x1,int &y1,int &x2,int &y2)

{

int K1=0,K2=0; // Variablen mit je 4 Flags für rechts, links, oben, unten.

int dx,dy;

dx=x2-x1; // Die Breite der Linie vorberechnen für spätere Koordinaten Interpolation

dy=y2-y1; // Die Höhe der Linie vorberechnen für spätere Koordinaten Interpolation

// Die folgende Abfrage setzt die Flags CLIPLEFT,CLIPRIGHT,CLIPUPPER,CLIPLOWER, falls die Koordinate

// auf einer oder zwei Seiten außerhalb des Clip Rechtecks liegt. Ein Punkt kann nicht gleichzeitig

// rechts und links (bzw. oben und unten) außerhalb liegen, daher können nur maximal 2 Flags gesetzt sein.

// Es gibt 9 Möglichkeiten. Davon sind 8 ungleich 0 und zeigen an, dass die Koordinate geclippt werden muss.

if(y1<YMin) K1 =CLIPLOWER; // Ermittle, wo der Anfangspunkt außerhalb des Clip Rechtecks liegt.

if(y1>YMax) K1 =CLIPUPPER; // Es werden entweder CLIPLOWER oder CLIPUPPER und/oder CLIPLEFT oder CLIPRIGHT gesetzt

if(x1<XMin) K1|=CLIPLEFT; // Es gibt 8 zu clippende Kombinationen, je nachdem in welchem der 8 angrenzenden

if(x1>XMax) K1|=CLIPRIGHT; // Bereiche des Clip Rechtecks die Koordinate liegt.

if(y2<YMin) K2 =CLIPLOWER; // Ermittle, wo der Endpunkt außerhalb des Clip Rechtecks liegt.

if(y2>YMax) K2 =CLIPUPPER; // Wenn keines der Flags gesetzt ist, dann liegt die Koordinate

if(x2<XMin) K2|=CLIPLEFT; // innerhalb des Rechtecks und muss nicht geändert werden.

if(x2>XMax) K2|=CLIPRIGHT;

// Schleife nach Cohen Sutherland, die maximal zweimal durchlaufen wird

while(K1 || K2) // muss wenigstens eine der Koordinaten irgendwo geclippt werden?

{

// wenn beide Koordinaten entweder links, rechts, über oder unter dem Clipping Rechteck liegen

// ist kein Teil der Linie sichtbar, daher ist keine weitere Berechnung notwendig.

// Die geclippte Linie ist unsichtbar.

if(K1 & K2) // logisches AND der beiden Koordinaten Flags ungleich 0?

return FALSE; // beide Punkte liegen jeweils auf der gleichen Seite außerhalb des Rechtecks

if(K1) // schnelle Abfrage, muss Koordinate 1 geclippt werden?

{

if(K1 & CLIPLEFT) // ist Anfangspunkt links außerhalb?

{ // ja

y1+=(XMin-x1)*dy/dx; // berechne y1 durch lineare Interpolation, dx kann hier nie 0 sein

x1=XMin; // setze x1 an den linken Rand des Clip Rechtecks

}

else if(K1 & CLIPRIGHT) // ist Anfangspunkt rechts außerhalb?

{ // ja

y1+=(XMax-x1)*dy/dx; // berechne y1 durch lineare Interpolation, dx kann hier nie 0 sein

x1=XMax; // setze x1 an den rechten Rand des Clip Rechtecks

}

if(K1 & CLIPLOWER) // ist Anfangspunkt unterhalb des Rechtecks?

{ // ja

x1+=(YMin-y1)*dx/dy; // berechne x1 durch lineare Interpolation, dy kann hier nie 0 sein

y1=YMin; // setze y1 an den unteren Rand des Clip Rechtecks

}

else if(K1 & CLIPUPPER) // ist Anfangspunkt oberhalb des Rechtecks?

{ // ja

x1+=(YMax-y1)*dx/dy; // berechne x1 durch lineare Interpolation, dy kann hier nie 0 sein

y1=YMax; // setze y1 an den oberen Rand des Clip Rechtecks

}

K1 = 0; // Erst davon ausgehen, dass der Punkt jetzt innerhalb liegt,

// falls das nicht zutrifft, wird gleich korrigiert.

if(y1<YMin) K1 =CLIPLOWER; // ermittle erneut, wo der Anfangspunkt jetzt außerhalb des Clip Rechtecks liegt

if(y1>YMax) K1 =CLIPUPPER; // Für einen Punkt, bei dem im ersten Durchlauf z. B. CLIPLEFT gesetzt war,

if(x1<XMin) K1|=CLIPLEFT; // kann im zweiten Durchlauf z. B. CLIPLOWER gesetzt sein

}

// muss hier nochmal getestet werden, sonst werden Linien, die über Eck außerhalb liegen nicht korrekt behandelt

if(K2) // schnelle Abfrage, muss Koordinate 2 geclippt werden?

{ // ja

if(K2 & CLIPLEFT) // liegt die Koordinate links außerhalb des Rechtecks?

{ // ja

y2+=(XMin-x2)*dy/dx; // berechne y durch lineare Interpolation, dx kann hier nie 0 sein

x2=XMin; // setze die x Koordinate an den linken Rand

}

else if(K2 & CLIPRIGHT) // liegt die Koordinate rechts außerhalb des Rechtecks?

{ // ja

y2+=(XMax-x2)*dy/dx; // berechne y durch lineare Interpolation, dx kann hier nie 0 sein

x2=XMax; // setze die x Koordinate an den rechten Rand

}

if(K2 & CLIPLOWER) // liegt der Endpunkt unten außerhalb des Rechtecks?

{ // ja

x2+=(YMin-y2)*dx/dy; // berechne x durch lineare Interpolation, dy kann hier nie 0 sein

y2=YMin; // setze die y Koordinate an den unteren Rand

}

else if(K2 & CLIPUPPER) // liegt der Endpunkt oben außerhalb des Rechtecks?

{ // ja

x2+=(YMax-y2)*dx/dy; // berechne x durch lineare Interpolation, dy kann hier nie 0 sein

y2=YMax; // setze die y Koordinate an den oberen Rand

}

K2 = 0; // Erst davon ausgehen, dass der Punkt jetzt innerhalb liegt,

// falls das nicht zutrifft, wird gleich korrigiert.

if(y2<YMin) K2 =CLIPLOWER; // ermittle erneut, wo der Endpunkt jetzt außerhalb des Clip Rechtecks liegt

if(y2>YMax) K2 =CLIPUPPER; // Ein Punkt, der z. B. zuvor über dem Clip Rechteck lag, kann jetzt entweder

if(x2<XMin) K2|=CLIPLEFT; // rechts oder links davon liegen. Wenn er innerhalb liegt wird kein

}

} // Ende der while Schleife, die Schleife wird maximal zweimal durchlaufen.

return TRUE; // jetzt sind die Koordinaten geclippt und die gekürzte Linie kann gezeichnet werden

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.cs.helsinki.fi/group/goa/viewing/leikkaus/lineClip.html">Beschreibung</a> (englisch)</li>

<li><a rel="nofollow" class="external text" href="https://pastehtml.com/view/awhhmf14g.html">JavaScript-Implementierung</a> (mit Quelltext)</li>

<li><a rel="nofollow" class="external text" href="https://min.nl/cs426/classes/clip.html">Java-Applet</a></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2023-11-20" href="https://de.wikipedia.org/wiki/?title=Algorithmus_von_Cohen-Sutherland&oldid=239314235">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>